// 在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。

// 返回重复了 N 次的那个元素。

//  

// 示例 1：

// 输入：[1,2,3,3]
// 输出：3
// 示例 2：

// 输入：[2,1,2,5,3,2]
// 输出：2
// 示例 3：

// 输入：[5,1,5,2,5,3,5,4]
// 输出：5
//  

// 提示：

// 4 <= A.length <= 10000
// 0 <= A[i] < 10000
// A.length 为偶数

#include <vector>
#include <unordered_set>

using namespace std;

// set中出现过的就直接返回
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        unordered_set<int> hashSet;
        for (int& num : nums) {
            if (hashSet.count(num) > 0) {
                return num;
            }
            hashSet.insert(num);
        }
        return -1;
    }
};

// 相同元素之间的间隔最大为1，直接比较相邻三个数是否相同
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        int n = nums.size();
        if (nums[0] == nums[n - 1]) { // 小心头尾相等的情况
            return nums[0];
        }
        for (int i{2}; i < n; ++i) {
            if (nums[i] == nums[i - 1] || nums[i] == nums[i - 2]) {
                return nums[i];
            }
        }
        return 0;
    }
};
